package string;

import java.util.Arrays;

/**
 * 在一个字符串中找到没有重复字符子串中最长的长度。
 * <p>
 * 例如:
 * abcabcbb没有重复字符的最长子串是abc，长度为3
 * bbbbb，答案是b，长度为1
 * pwwkew，答案是wke，长度是3
 * 要求:答案必须是子串，"pwke”是一个子字符序列但不是一个子字符串。
 *
 * @author Liaorun
 */
public class LongestNoRepeatSubstring {

    public static void main(String[] args) {
        System.out.println(maxUnique("abcabcbb"));
        System.out.println(maxUnique("bbbbb"));
        System.out.println(maxUnique("pwwkew"));
    }

    public static int maxUnique(String str) {
        if (str == null || str.isEmpty()) {
            return 0;
        }

        char[] chars = str.toCharArray();

        // map 代替了哈希表 假设字符的码是0~255
        int[] map = new int[256];

        Arrays.fill(map, -1);

        // 有重复字符的最长子串的长度
        int len = 0;
        int pre = -1;
        int cur = 0;
        for (int i = 0; i < chars.length; i++) {
            // 这个字符前一次出现的位置，和上一个字符前一次出现的位置，谁大记录谁
            pre = Math.max(pre, map[chars[i]]);
            // cur = 当前字符没有重复字符的最长子串的长度 pre..i
            cur = i - pre;
            // 当前字符结尾的字符串，不重复的最大长度是否是最好结果
            // 是就更新长度记录
            len = Math.max(len, cur);
            map[chars[i]] = i;
        }

        return len;
    }
}
